#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
    {
        int mi = obstacleGrid.size();
        int mj = obstacleGrid[0].size();
        if (obstacleGrid[0][0] == 1 || obstacleGrid[mi - 1][mj - 1] == 1)
            return 0;
        vector<vector<int>> dp(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(), -1));
        dp[mi - 1][mj - 1] = 1;
        for (int i = mi - 2; i >= 0; i--)
            dp[i][mj - 1] = obstacleGrid[i][mj - 1] == 1 ? 0 : dp[i + 1][mj - 1];
        for (int j = mj - 2; j >= 0; j--)
            dp[mi - 1][j] = obstacleGrid[mi - 1][j] == 1 ? 0 : dp[mi - 1][j + 1];
        return minPathSum(dp, obstacleGrid, 0, 0);
    }

    int minPathSum(vector<vector<int>> &dp, vector<vector<int>> &obs, int i, int j)
    {
        if (dp[i][j] != -1)
            return dp[i][j];
        if (obs[i][j] == 1)
            dp[i][j] = 0;
        else
            dp[i][j] = minPathSum(dp, obs, i, j + 1) + minPathSum(dp, obs, i + 1, j);
        return dp[i][j];
    }
};
int main()
{
    cout << "Code63" << endl;
    Solution s;
    vector<vector<int>> grid = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
    cout << s.uniquePathsWithObstacles(grid) << endl;
    return 0;
}